#pragma region
typedef struct
{
    int weight;
    int parent;
    int lchild;
    int rchild;
} HNodeType;
HNodeType HFMTree[2 * n - 1];

//【算法4 - 20】哈夫曼树的构造
#define MAXVALUE 10000 //为找最小，定义一个较大的数
void Create _HuffMTree(HNodeType HFMTree[], int n)
{ //构造的哈夫曼树存储于HFMTree [ ] ，n为叶子结点的个数
    int m1, x1, m2, x2;
    // x1和x2存储最小和次最小权值，m1和m2存储其位置
    int i, j;
    for (i = 0; i < 2 * n - 1; i++) // HFMTree初始化
    {
        HuffMTree[i].weight = 0;
        HFMTree[i].parent = -1;
        HFMTree[i].lchild = -1;
        HFMTree[i].rchild = -1;
    }
    for (i = 0; i < n; i++)
        scanf("%d", &HFMTree[i].weight);
    //输入n个叶子结点的权值,设为整型
    for (i = 0; i < n - 1; i++) //构造哈夫曼树
    {
        x1 = x2 = MAXVALUE;
        m1 = m2 = 0;
        for (j = 0; j < n + i; j++)
        {
            if (HFMTree[j].parent == -1 && HFMTree[j].weight < x1)
            { // 找出根结点具有最小和次最小权值的两棵树
                x2 = x1;
                m2 = m1;
                x1 = HFMTree[j].weight;
                m1 = j;
            }
            else if (HFMTree[j].parent == -1 && HFMTree[j].weight < x2)
            {
                x2 = HFMTree[j].weight;
                m2 = j;
            }
        }
        //将找出的两棵子树合并为一棵子树
        HFMTree[m1].parent = n + i;
        HFMTree[m2].parent = n + i;
        HFMTree[n + i].weight = FMTree[m1].weight + HFMTree[m2].weight;
        HFMTree[n + i].lchild = m1;
        HFMTree[n + i].rchild = m2;
    }
}
#pragma endregion
#pragma region
typedef struct
{
    int bit[n]; // n为叶结点的个数，设为已知
    int start;
} HCodeType;
HCodeType HuffCode[n]; //各字符得编码

//【算法4 - 21】哈夫曼编码
Void HaffmanCode(HNodeType HFMTree[], HCodeType HuffCode[])
{
    HCodeType cd; //字符编码的缓冲变量
    int i, j, c, p;
    for (i = 0; i < n; i++) //求每个叶子结点的哈夫曼编码
    {
        cd.start = n - 1;
        c = i;
        p = HFMTree[c].parent;
        while (c.parent != -1) //由叶子结点向上直到树根
        {
            if (HFMTree[p].lchild == c)
                cd.bit[cd.start] = 0;
            else
                cd.bit[cd.start] = 1;
            cd.start - -;
            c = p;
            p = HFMTree[c].parent;
        }
        for (j = cd.start + 1; j < n; j++)
            //保存求出的每个叶结点的哈夫曼编码和编码起始位
            HuffCode[i].bit[j] = cd.bit[j];
        HuffCode[i].start = cd.start + 1;
    }
}
#pragma endregion
#pragma region
#define MAXNODE 1024
//树中结点的最大个数，可根据实际情况进行修改
typedef struct
{
    datatype data;
    int parent;
} PNode;
PNode t[MAXNODE];
#pragma endregion

#pragma region 【算法4 - 22】集合并运算
void Union(NodeType a[] ，int i，int j)
{ //合并以数组a第i个元素和第j个元素为根结点的集合
    if (a[i].parent != -1 || a[j].parent != -1)
    {
        printf("\n调用参数不正确");
        return；
    }
    a[j].parent = i; //将i置为两个集合共同的根结点
}

//如果要查找某个元素所在的集合，可以沿着该元素的双亲域向上查，当查到某个元素的双亲域值为－1时，该元素就是所查元素所属集合的树根结点，算法如下：
//【算法4 - 23】查找集合体
int Find(NodeType a[], elemtype x)
{ //在数组a中查找值为x的元素所属的集合，若找到，返回树根结点在数组a中的序号；
  //否则，返回-1常量MAXNODE为数组a的最大容量
    int i = 0, j;
    while (i < MAXNODE && a[i].data != x)
        i++;
    if (i >= MAXNODE)
        return -1;
    //值为x的元素不属于该组集合，返回－1
    j = i;
    while (a[j].parent != -1)
        j = a[j].parent;
    return j; // j为该集合的树根结点在数组a中的序号
}
#pragma endregion